//给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 
//
// 
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 
//
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
//输出：4
//解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
//其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 
//n 的值 3 。
// 
//
// 示例 2： 
//
// 
//输入：strs = ["10", "0", "1"], m = 1, n = 1
//输出：2
//解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= strs.length <= 600 
// 1 <= strs[i].length <= 100 
// strs[i] 仅由 '0' 和 '1' 组成 
// 1 <= m, n <= 100 
// 
// Related Topics 数组 字符串 动态规划 👍 746 👎 0


package leetcode.editor.cn;

/**
 * 一和零
 * @date 2022-06-29 14:02:32
 */
class P474_OnesAndZeroes{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P474_OnesAndZeroes().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/**
	 *这题倒序来优化空间我想了很久终于明白了： 1.首先“记录本”不一样了，我本来应该拿三维数组记录的，比如dp[i][m][n]代表前i个字符满足m个0，n个0的最大子集数，这时候我们就顺着来，因为每一个层数我们都会记录，但是递推公式发现只和上一层有关，也就是dp[i][m][n]只和dp[i-1][][]这一层的有关，那么就进行优化。 2.我只用一个二维的“记录本”来记录上一层，也就是dp[m][n]代表的意义是上一层满足m个0和n个1的最大子集数，我没法找到任意一层了，
	 * 因为我现在只有一个更小的“记录本”，所以我要保证算的过程中，永远能用上一层的数据，我就必须得倒着来，因为正着来的时候，我算dp[m][n] = dp[m-zeros][n-ones]就错了，
	 * 因为本来要用上一次赋值了的dp[m-zeros][n-ones]结果，你在这一层遍历先赋值了他们，后来才算的dp[m][n]，乱了，上一层数据没了，给你盖住了！
	 * 总之，倒序的目的就是少用一维数组，省下了空间，因为记录那么多层没必要，我只要上一层就ok。
	 *假设顺序遍历, zeros = 3 , ones = 5, i = 3, j = 5. 由dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones]),
	 * 得到dp[3][5] = max(dp[3][5], dp[0][0]), 那么dp[3][5] !可能! 就在这里被改变了(变成了dp[0][0]). 当i = 6, j = 8时, dp[i][j] = dp[6][8] = max(dp[6][8], dp[3][5]),
	 * 这里的dp[3][5]是在这一轮最外层循环中被改变的dp[3][5], 并不是我们想要的上一次最外层循环中的dp[3][5]
	 *
	 */
    public int findMaxForm(String[] strs, int m, int n) {//m-0 n-1
		int[][] dp = new int[m+1][n+1];
		for (String str : strs) {
			int oneNum = 0,zeroNum = 0;
			for (char c : str.toCharArray()){
				if(c == '0'){
					zeroNum++;
				}else{
					oneNum++;
				}
			}
			for (int i = m; i >= zeroNum; i--) {
				for (int j = n; j >= oneNum; j--) {
					dp[i][j] = Math.max(dp[i][j],dp[i - zeroNum][j - oneNum] + 1);
				}
			}
		}
		return dp[m][n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
